Sa standardnog ulaza se dobija niz celih brojeva, a zatim i m upita tipa l d promena, za svaki upit promeniti sve elemente niza čiji su indeksi u intervalu [l,d] za vrednost promena. Vremenska složenost algoritma treba biti O(n + m).

Ulaz

Sa standardnog ulaza se dobija broj n ∈ [2,10⁵], i n brojeva iz intervala [−100,100]. Zatim se dobija broj m ∈ [2,10⁵] i toliko upita oblika ldp.

Izlaz

Ispisati izmenjene elemente pocetnog niza nakon svih izmena.

Primer 1

Ulaz

5
1 2 3 4 5
2
0 1 5
1 3 -5

Izlaz

6 2 -2 -1 5

Primer 2

Ulaz

5
0 0 0 0 0
3
0 4 1
1 3 2
0 4 -5

Izlaz

-4 -2 -2 -2 -4